<?php
/**
 * 二叉排序树/二叉搜索树
 */

namespace Xxb\XxbPhpAlgo;

use Xxb\XxbPhpAlgo\Contract\XxbBinaryTreeInterface;

class BinarySortTree implements XxbBinaryTreeInterface
{
    /**
     * 根结点
     * @var BinaryTreeNode|null
     */
    private $root;

    private $size;

    /**
     * 被删除的结点
     * @var BinaryTreeNode|null
     */
    private $shiftNode;

    public function __construct()
    {
        $this->root = null;
        $this->size = 0;
    }

    public function isEmpty()
    {
        return $this->size == 0;
    }

    public function getSize()
    {
        return $this->size;
    }

    public function add($value)
    {
        $this->loopAdd($value);
        //$this->root = $this->recurseAdd($this->root, $value);
    }

    /**
     * 以循环的方式添加结点
     * @param $value
     */
    public function loopAdd($value)
    {
        $node = new BinaryTreeNode($value);
        if (empty($this->root)) {
            $this->root = $node;
            $this->size++;
        } else {
            $cursor = $this->root;
            while (true) {
                if ($value > $cursor->getValue()) { // 找cursor的左子树
                    if (empty($cursor->getRight())) {
                        $cursor->setRight($node);
                        $this->size++;
                        break;
                    } else {
                        $cursor = $cursor->getRight();
                    }
                } elseif ($value < $cursor->getValue()) { // 找cursor的右子树
                    if (empty($cursor->getLeft())) {
                        $cursor->setLeft($node);
                        $this->size++;
                        break;
                    } else {
                        $cursor = $cursor->getLeft();
                    }
                } else {
                    break;
                }
            }
        }
    }

    /**
     * 通过递归添加结点
     * @param BinaryTreeNode|null $node
     * @param                $value
     *
     * @return BinaryTreeNode
     */
    public function recurseAdd($node, $value)
    {
        if (is_null($node)) {
            $this->size++;
            return new BinaryTreeNode($value);
        }

        if ($value > $node->getValue()) {
            // 往该结点的右边找
            $node->setRight($this->recurseAdd($node->getRight(), $value));
        } elseif ($value < $node->getValue()) {
            // 往该结点的左边找
            $node->setLeft($this->recurseAdd($node->getLeft(), $value));
        }
        // 和结点值相等则不添加

        // 本次递归结束 还需返回当前结点 否则树就会断开
        return $node;
    }

    /**
     * 删除结点：
     * 叶子结点直接删除
     * 删除只有一颗子树的结点：让子树替换它(要注意是左子树还是右子树)
     * 删除2棵子树的结点：
     * 找左子树的最大值顶替它
     * 或者找右子树的最小值顶替它
     * @param $value
     *
     * @return BinaryTreeNode|null
     */
    public function shift($value)
    {
        if ($this->isEmpty()) {
            throw new \RuntimeException('remove error, tree is empty.');
        }
        //return $this->loopShift($value);
        $this->root = $this->recurseShift($this->root, $value);
        return $this->shiftNode;
    }

    /**
     * 通过循环的方式删除结点
     * @param $value
     *
     * @return mixed|BinaryTreeNode|null
     */
    private function loopShift($value)
    {
        $shiftNode = $this->search($value); // 查找被删除的结点
        if (is_null($shiftNode)) {
            // 没有找到删除结点
            return null;
        }

        $shiftNodeParent = $this->searchParent($value);
        if (is_null($shiftNode->getLeft()) && is_null($shiftNode->getRight())) {
            if ($shiftNode === $this->root) {
                $this->root = null;
            } else if ($shiftNodeParent->getLeft() === $shiftNode) {
                // 删除的叶子结点在左边
                $shiftNodeParent->setLeft(null);
            } else {
                // 删除的叶子结点在右边
                $shiftNodeParent->setRight(null);
            }
            $this->size--;
        } elseif (!is_null($shiftNode->getLeft()) && !is_null($shiftNode->getRight())) {
            // 删除的结点有2棵子树
            $rightMinNode = $this->getRightMinNode($shiftNode->getRight());
            // 右子树上的最小结点替代删除结点
            $newNode = new BinaryTreeNode($rightMinNode->getValue());
            $this->loopShift($rightMinNode->getValue()); // 删除右子树的最小结点
            $newNode->setLeft($shiftNode->getLeft());
            $newNode->setRight($shiftNode->getRight());
            // 父结点重新指向替代的结点
            if ($shiftNode === $this->root) {
                $this->root = $newNode;
            } else {
                if ($shiftNodeParent->getLeft() === $shiftNode) {
                    $shiftNodeParent->setLeft($newNode);
                } else {
                    $shiftNodeParent->setRight($newNode);
                }
            }
            $shiftNode->setLeft(null);
            $shiftNode->setRight(null);
            $this->size--;
        } else {
            // 删除的结点只有一棵子树
            if (!is_null($shiftNode->getLeft())) {
                // 被删除结点左子树不为空
                if ($shiftNode === $this->root) {
                    $this->root = $shiftNode->getLeft();
                } else if ($shiftNodeParent->getLeft() === $shiftNode) {
                    $shiftNodeParent->setLeft($shiftNode->getLeft());
                } else {
                    $shiftNodeParent->setRight($shiftNode->getLeft());
                }
                $shiftNode->setLeft(null);
            } else {
                // 被删除结点右子树不为空
                if ($shiftNode === $this->root) {
                    $this->root = $shiftNode->getRight();
                } else if ($shiftNodeParent->getLeft() === $shiftNode) {
                    $shiftNodeParent->setLeft($shiftNode->getRight());
                } else {
                    $shiftNodeParent->setRight($shiftNode->getRight());
                }
                $shiftNode->setRight(null);
            }
            $this->size--;
        }

        return $shiftNode;
    }

    /**
     * 通过递归方式删除结点
     * @param BinaryTreeNode|null $node
     * @param $value
     *
     * @return mixed
     */
    private function recurseShift($node, $value)
    {
        if (is_null($node)) {
            return null;
        }

        if ($value < $node->getValue()) {
            $node->setLeft($this->recurseShift($node->getLeft(), $value));
        } else if ($value > $node->getValue()) {
            $node->setRight($this->recurseShift($node->getRight(), $value));
        } else {
            // 删除结点
            if (is_null($node->getLeft()) && is_null($node->getRight())) {
                // 删除的是叶子结点
                $this->shiftNode = $node;
                $this->size--;
                return null;
            } else if (!is_null($node->getLeft()) && !is_null($node->getRight())) {
                // 删除的结点有2棵子树，往右子树上找最小值结点替换它
                $minNode = $this->getRightMinNode($node->getRight());
                $minNode->setRight($this->recurseShift($node->getRight(), $minNode->getValue()));
                $minNode->setLeft($node->getLeft());
                $node->setLeft(null);
                $node->setRight(null);
                $this->shiftNode = $node;
                return $minNode;
            } else {
                // 删除的结点只有一棵子树
                $this->shiftNode = $node;
                if (!is_null($node->getLeft())) {
                    $retNode = $node->getLeft();
                    $node->setLeft(null);
                    $this->size--;
                    return $retNode;
                } else {
                    $retNode = $node->getRight();
                    $node->setRight(null);
                    $this->size--;
                    return $retNode;
                }
            }
        }

        return $node;
    }

    /**
     * 查找指定结点为根的子树上的最小值：
     * 根据二叉排序树的特点，这个最小值结点肯定是叶子结点
     * 因此只要往这棵树的最左边找就能找到
     *
     * @param BinaryTreeNode $node
     *
     * @return BinaryTreeNode
     */
    private function getRightMinNode(BinaryTreeNode $node)
    {
        if (is_null($node->getLeft()) && is_null($node->getRight())) {
            return $node;
        }
        return $this->getRightMinNode($node->getLeft());
    }

    /**
     * 借助栈实现前序遍历
     * @return array
     */
    public function previousTraversal()
    {
        if ($this->isEmpty()) {
            return [];
        }
        $result = [];
        $stack = new \SplStack();
        $stack->push($this->root);
        while (!$stack->isEmpty()) {
            /** @var $node BinaryTreeNode */
            $node = $stack->pop();
            $result[] = $node->getValue();
            if (!is_null($node->getRight())) {
                $stack->push($node->getRight());
            }
            if (!is_null($node->getLeft())) {
                $stack->push($node->getLeft());
            }
        }
        return $result;
    }

    /**
     * 递归实现前序遍历
     * @param null  $node
     * @param array $result
     *
     * @return array|mixed
     */
    public function recursePreviousTraversal($node = null, &$result = [])
    {
        if ($this->isEmpty()) {
            return [];
        }
        if (is_null($node)) {
            $node = $this->root;
        }
        $result[] = $node->getValue();
        if (is_null($node->getLeft()) && is_null($node->getRight())) { // 遍历到了叶子结点
            return [];
        }
        !is_null($node->getLeft()) && $this->recursePreviousTraversal($node->getLeft(), $result);
        !is_null($node->getRight()) && $this->recursePreviousTraversal($node->getRight(), $result);
        return $result;
    }

    /**
     * 借助队列实现中序遍历
     * @return array
     */
    public function middleTraversal()
    {
        if ($this->isEmpty()) {
            return [];
        }
        $result = [];
        $queue = new \SplQueue();
        $queue->push($this->root->getLeft());
        $queue->push($this->root);
        $queue->push($this->root->getRight());
        while (!$queue->isEmpty()) {
            /** @var $node BinaryTreeNode */
            $node = $queue->shift();
            if (is_null($node)) {
                continue;
            }
            if (is_null($node->getLeft()) && is_null($node->getRight())) { // 叶子结点
                $result[] = $node->getValue();
                continue;
            } else {
                if (!$queue->isEmpty()
                    && (is_null($queue->bottom()) || $queue->bottom() == $node->getRight())) {
                    $result[] = $node->getValue();
                    continue;
                }
                $queue->unshift($node->getRight());
                $queue->unshift($node);
                $queue->unshift($node->getLeft());
            }
        }
        return $result;
    }

    /**
     * 递归实现中序遍历
     * @param null  $node
     * @param array $result
     *
     * @return array|mixed
     */
    public function recurseMiddleTraversal($node = null, &$result = [])
    {
        if ($this->isEmpty()) {
            return [];
        }
        if (is_null($node)) {
            $node = $this->root;
        }
        !is_null($node->getLeft()) && $this->recurseMiddleTraversal($node->getLeft(), $result);
        $result[] = $node->getValue();
        !is_null($node->getRight()) && $this->recurseMiddleTraversal($node->getRight(), $result);
        return $result;
    }

    public function afterTraversal()
    {
        if ($this->isEmpty()) {
            return [];
        }
        $result = [];
        $preDequeueNode = null;
        $queue = new \SplQueue();
        !is_null($this->root->getLeft()) && $queue->push($this->root->getLeft());
        !is_null($this->root->getRight()) && $queue->push($this->root->getRight());
        $queue->push($this->root);

        while (!$queue->isEmpty()) {
            /** @var  $bottom BinaryTreeNode */
            $bottom = $queue->bottom();
            if ((is_null($bottom->getLeft()) && is_null($bottom->getRight())) || $bottom->getRight() === $preDequeueNode) {
                // 叶子结点 或者 队头结点的右孩子结点==上一个出队元素 直接出队
                $queue->shift();
                $result[] = $bottom->getValue();
                $preDequeueNode = $bottom;
                continue;
            }

            if (!is_null($bottom->getRight())) {
                $queue->unshift($bottom->getRight());
            }
            if (!is_null($bottom->getLeft())) {
                $queue->unshift($bottom->getLeft());
            }
        }

        return $result;
    }

    /**
     * 递归实现后序遍历
     * @param null  $node
     * @param array $result
     *
     * @return array|mixed
     */
    public function recurseAfterTraversal($node = null, &$result = [])
    {
        if ($this->isEmpty()) {
            return [];
        }

        if (is_null($node)) {
            $node = $this->root;
        }

        !is_null($node->getLeft()) && $this->recurseAfterTraversal($node->getLeft(), $result);
        !is_null($node->getRight()) && $this->recurseAfterTraversal($node->getRight(), $result);
        $result[] = $node->getValue();
        return $result;
    }

    /**
     * 通过队列实现层级遍历：
     * 从上至下逐层遍历，每一层从左至右遍历
     * @return array
     */
    public function hierarchicalTraversal()
    {
        if (is_null($this->root)) {
            return [];
        }

        $result = [];
        $queue = new \SplQueue();
        $queue->push($this->root);
        while (!$queue->isEmpty()) {
            /** @var $node BinaryTreeNode */
            $node = $queue->shift();
            $result[] = $node->getValue();
            if (!is_null($node->getLeft())) {
                $queue->push($node->getLeft());
            }
            if (!is_null($node->getRight())) {
                $queue->push($node->getRight());
            }
        }

        return $result;
    }

    public function search($value)
    {
        return $this->searchNode($this->root, $value);
    }

    public function searchParent($value)
    {
        return $this->searchParentNode($this->root, $value);
    }

    /**
     * 查找以root为根的树：
     * 1. 如果查找的值大于当前根结点的值，则继续往右找
     * 2. 如果查找的值小于当前根结点的值，则继续往左找
     * 3. 相等则返回
     * @param BinaryTreeNode|null $root
     * @param                $value
     *
     * @return BinaryTreeNode|null
     */
    private function searchNode($root, $value)
    {
        if (is_null($root)) {
            return null;
        }

        if ($value > $root->getValue()) {
            return $this->searchNode($root->getRight(), $value);
        } elseif ($value < $root->getValue()) {
            return $this->searchNode($root->getLeft(), $value);
        } else {
            return $root;
        }
    }

    /**
     * 查找以root为根的树：
     * 1. 如果查找的值等于左孩子结点或者右孩子结点值，则返回该结点
     * 2. 否则往左或者往右接着找
     * 3. 如果查找值等于当前结点的值，则返回空，说明查找值没有父结点
     * @param BinaryTreeNode $root
     * @param                $value
     *
     * @return BinaryTreeNode|null
     */
    private function searchParentNode(BinaryTreeNode $root, $value)
    {
        if (is_null($root)) {
            return null;
        }

        if (
            (!is_null($root->getLeft()) && $value == $root->getLeft()->getValue())
            || (!is_null($root->getRight()) && $value == $root->getRight()->getValue())) {
            return $root;
        }

        if ($value < $root->getValue()) {
            return $this->searchParentNode($root->getLeft(), $value);
        } elseif ($value > $root->getValue()) {
            return $this->searchParentNode($root->getRight(), $value);
        } else {
            return null;
        }
    }
}
